'''
计算最大公约数gcd(Greatest Common Divisor)和最小公倍数lcm(Lowest Common Multiple)
最大公约数: 也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。形式化表示: (a,b);函数表示：gcd(a,b)
最小公倍数: 两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。形式化表示：[a,b];函数表示: lcm(a,b)
最大公约数与最小公倍数的关系: (a, b) * [a, b] = a * b
测试用例：
98, 63: gcd=7, lcm=882
30, 45: gcd=15, lcm=90
'''

'''
最大公约数：辗转相除法（欧几里德算法）
原理:
设整数a，b
1. a，b与 a mod b具有相同的最大公约数。即两个数与两个数的余数具有相同的最大公约数
2. 任何整数与零的最大公约数是这个数
'''
def euclidean_gcd(a:int, b:int):
    if b == 0:
        return a
    m = a % b
    print(f'{a} % {b} = {m}')
    return euclidean_gcd(b, m)

'''
最大公约数：暴力法
'''
def force_gcd(a:int, b:int):
    if a == b:
        return a
    m = b if a > b else a
    for i in range(m, 0, -1):
        if a % i == 0 and b % i == 0:
            return i

'''
最小公倍数: 公式法
lcm = a * b / gcd(a, b)
'''
def formula_lcm(a:int, b:int):
    return a * b // euclidean_gcd(a, b) # 使用整除

'''
最小公倍数: 暴力法
'''
def force_lcm(a:int, b:int):
    m = a if a > b else b
    while True:
        if m % a == 0 and m % b == 0:
            return m
        m += 1

a = int(input('请输入第一个整数：'))
b = int(input('请输入第二个整数：'))
gcd = euclidean_gcd(a, b)
#gcd = force_gcd(a, b)
lcm = formula_lcm(a, b)
#lcm = force_lcm(a, b)

print(f'{a},{b}的最大公约数是：{gcd}')
print(f'{a},{b}的最小公倍数是：{lcm}')
